package simple;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

/**
 *
 * 给你两个整数数组nums1 和 nums2 ，请你以数组形式返回两数组的交集。
 * 返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。
 * 可以不考虑输出结果的顺序。
 *
 * 链接：https://leetcode-cn.com/problems/intersection-of-two-arrays-ii
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class IntersectionOfTwoArraysII {
    /**
     *  20:26 ~ 20:49  17min
     * 我能想到的最简单的方式 时间复杂度为O(n*m) 其中n为num1的长度 m为num2的长度
     * 将nums1作为最外层的循环，nums2作为内层的循环。
     * 对两个数进行比较。如果相同，则将该数插入到结果数组中。并且将nums1 和 nums2中该数置为-1（因为该题的元素范围>=0）
     * */
    class Solution {
        public int[] intersect(int[] nums1, int[] nums2) {
            ArrayList<Integer> result = new ArrayList<>();
            for (int i = 0; i < nums1.length; i++) {
                for (int j = 0; j < nums2.length; j++) {
                    if(nums1[i] == -1){
                        break;
                    }
                    if(nums1[i] == nums2[j]){
                        result.add(nums1[i]);
                        nums1[i] = -1;
                        nums2[j] = -1;
                    }
                }
            }
            return result.stream().mapToInt(Integer::valueOf).toArray();
        }
    }

    /**
     * 时间复杂度 O(m+n)  5ms
     * 借助HashMap来记录nums1中元素出现的次数。
     * 然后我们使用nums2的元素去跟HashMap中的元素进行比较，
     * 如果说存在，且次数>0,那就将其加入到结果中。并将该数在HashMap的次数-1
     *
     * ps:该方法也适合 nums2为即时输入 或者 磁盘上不能一次读取到内存的方法
     * */
    class Solution1 {
        public int[] intersect(int[] nums1, int[] nums2) {
            HashMap<Integer,Integer> hashMap = new HashMap<>();
            List<Integer> list = new ArrayList<>();
            for (int num : nums1){
                hashMap.put(num,hashMap.getOrDefault(num,0) + 1);
            }
            for(int num : nums2){
                if(hashMap.containsKey(num) && hashMap.get(num) > 0){
                    list.add(num);
                    hashMap.put(num,hashMap.get(num)-1);
                }
            }
            return list.stream().mapToInt(Integer::valueOf).toArray();
        }
    }

    /**
     * 2ms
     * 排序 + 双指针  时间复杂度O(mlogm + nlogn)
     * 感觉使用数组 比 用list省出来一半时间
     * */
    class Solution2 {
        public int[] intersect(int[] nums1, int[] nums2) {
            Arrays.sort(nums1);
            Arrays.sort(nums2);
            int i = 0;
            int j = 0;
            int index = 0;
            int[] result = new int[Math.max(nums1.length, nums2.length)];
            while(i < nums1.length && j < nums2.length){
                if(nums1[i] == nums2[j]){
                    result[index++] = nums1[i];
                    i++;
                    j++;
                } else {
                    int t = nums1[i] > nums2[j] ? j++ : i++;
                }
            }
            return Arrays.copyOfRange(result, 0, index);
        }
    }
}
